1. Field of the Invention
This invention relates to a binary tree arrangement storing fixed or variable length keys, and a method and apparatus for locating the insert arc or node in such an arrangement.
2. Introduction
The invention provides a novel binary tree arrangement for a machine representation storing both fixed and variable length keys, together with their lengths, organized by the nodes and connections between nodes in said binary tree. The arrangement minimizes the storage required for the machine representation of said nodes, connections, keys and their lengths.
The invention provides method and means for controlling the locating step(s) of a binary tree insertion operation, It uses a principle based on a minimal difference or a maximal similarity relationship among the keys stored in the tree.
The embodiments of this invention include unique methods and apparatus for controlling the execution of a computer. This application describes the steps performed and the machine representation in sufficient detail that a person skilled in the art can make and use them in hardware, microprogram, or program. Thus the inventions can be utilized in either a special purpose or general purpose computer system.
The invention provides the control logic for said insertion method in a binary tree having said novel binary tree arrangement, said control logic minimizing the number of storage accesses and stores for carrying out said locating step(s) and inserting operation, and minimizing the amount of elapsed time required for a machine to execute said operations.
The invention provides both method and means for said control logic that is especially suited for direct use in a special purpose apparatus for executing the subject processes, and especially suited for incorporation in a reduced instruction set computer (RISC) in the form of instructions which can be executed in a single cycle.
The methods and apparatus of the invention provide economic advantage for sorting and indexing, which are heavily used in commercial computing environments; especially providing a competitive economic advantage for computer execution of database operations and associative classes in object oriented programming, logic programming, and constraint logic programming.